package competition;

import java.util.Arrays;

/**
 * 10.31力扣竞赛
 *
 * @author 23737
 * @time 2021.10.31
 */
public class October_31 {
    public static void main(String[] args) {

    }
}

/**
 * . 间隔删除链表结点
 * 给你一个链表的头结点 head，每隔一个结点删除另一个结点（要求保留头结点）。
 * 请返回最终链表的头结点。
 */
class One {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(5);
        ListNode listNode2 = new ListNode(1);
        ListNode listNode3 = new ListNode(8);
        ListNode listNode4 = new ListNode(6);
        ListNode listNode5 = new ListNode(9);
        listNode.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode listNode1 = new Solution().deleteListNode(listNode);
        while (listNode1 != null) {
            System.out.println(listNode1.val);
            listNode1 = listNode1.next;
        }

        ListNode listNode11 = new ListNode(1);
        ListNode listNode22 = new ListNode(2);
        ListNode listNode33 = new ListNode(3);
        ListNode listNode44 = new ListNode(4);
        listNode11.next = listNode22;
        listNode22.next = listNode33;
        listNode33.next = listNode44;
        new Solution().deleteListNode(listNode11);
        while (listNode11 != null) {
            System.out.println(listNode11.val);
            listNode11 = listNode11.next;
        }
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

/**
 * 个人解法
 */
class Solution {
    public ListNode deleteListNode(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode listNode = head;
        ListNode pre = listNode;
        while (listNode != null) {
            if (listNode.next == null) break;
            listNode.next = listNode.next.next;
            listNode = listNode.next;
        }
        return pre;
    }
}

/**
 * 某柱状图上共有 N 个柱形，数组 heights 中按照排列顺序记录了每个柱形的高度。假定任选 cnt 个柱形可组成一个柱形组，
 * 请在所有可能的柱形组中，找出最大高度与最小高度的差值为最小的柱形组，按高度升序返回该柱形组。
 * 若存在多个柱形组满足条件，则返回第一个元素最小的柱形组。
 */
class Two {
    public static void main(String[] args) {
        int[] a = new int[]{4, 6, 1, 8, 4, 10};
        int[] b = new int[]{3,2,7,6,1,8};
//        int[] ints = new Two().analysisHistogram(a, 4);
        int[] ints2 = new Two().analysisHistogram(b, 3);
        for (int i : ints2) {
            System.out.println(i);
        }
//        for (int anInt : ints) {
//            System.out.println(anInt);
//        }
    }

    //用的是滑动窗口相关知识点
    public int[] analysisHistogram(int[] heights, int cnt) {
        Arrays.sort(heights);
        int[] result = new int[cnt];
        int min = heights[cnt - 1] - heights[0];
        int store1 = 0;
        int store2 = cnt-1;
        for (int i = 0, j = cnt-1; i < heights.length && j< heights.length; i++, j = i+cnt-1) {
            if (min > heights[j] - heights[i]) {
                min = heights[j] - heights[i];
                store1 = i;
                store2 = j;
            }
        }
        int j = 0;
        for (int i = store1; i <= store2; i++) {
           result[j] = heights[i];
           j++;
        }
        return result;
    }
}

